package 贪心算法;

import java.util.Arrays;

public class 用最少数量的箭引爆气球 {
   static class Solution{
       public int findMinArrowShots(int[][] points){
          if (points.length==0) return 0;
          //这个lambda就是想按照第一维来排序
           Arrays.sort(points,((o1, o2) -> Integer.compare(o1[0],o2[0])));
            int count=1; //point不为空至少需要一支箭
           for (int i = 1; i < points.length; i++) {
               //气球i和气球i-1不挨着，注意这里不是>=
               //我的理解是没有挨着就是说两个之间没有覆盖一起，所以是需要两条件
               if (points[i][0]>points[i-1][1]){
                   count++;
               }else {
                   //气球i和气球i-1挨着
                   //然而挨着一起就证明只需要一支箭 所以不需要加了 同时更新重叠气球最小右边界
                   //我的理解是 重新更新当前最小的右边界 意义是 到下一个循环就会继续比较 然后判断是否需要加
                   points[i][1] = Math.min(points[i-1][1],points[i][1]);
               }
           }
           return count;
       }
   }

}
